#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"

void InitHeap(Heap* ph)
{
	assert(ph);
	int* tmp = (int*)malloc(sizeof(int)*4);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	ph->a = tmp;
	ph->size = 0;
	ph->capacity = 4;
}

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else return;
	}
}

void AdjustDown(int* a,int size)
{
	int parent = 0;
	int child1 = parent * 2 + 1, child2 = parent * 2 + 2;
	while (child1<size)
	{
		int tmp = a[child1] > a[child2] ? child1 : child2;
		if (tmp == size)
			tmp = child1;
		Swap(&a[tmp], &a[parent]);
		parent = tmp;
		child1 = parent * 2 + 1, child2 = parent * 2 + 2;
	}
}

void PushHeap(Heap* ph,int x)
{
	assert(ph);
	if (ph->capacity == ph->size)
	{
		int* tmp = (int*)realloc(ph->a,sizeof(int) * ph->capacity * 2);
		if (!tmp)
		{
			perror("realloc fail");
			return;
		}
		ph->a = tmp;
		ph->capacity *= 2;
	}
	ph->a[ph->size] = x;
	ph->size++;
	AdjustUp(ph->a,ph->size-1);
}

void PopHeap(Heap* ph)
{
	ph->size--;
	Swap(&ph->a[0], &ph->a[ph->size]);
	AdjustDown(ph->a,ph->size);
}